Conventional serial operated computers are derived from the architecture developed by John von Neumann. While this is by far the predominant type of computer, the limitations of this type of architecture for certain applications is leading the computer industry towards investigation of newer, more efficient types of parallel processors. The problem with the von Neumann computer architecture is that data are retrieved from a central memory, operated on and then returned to the memory. For many applications this is a slow and inefficient procedure, since a computer expends a great deal of its time merely retrieving and storing data.
A number of parallel processing architectures have been proposed to overcome the deficiencies of the serial computer. These generally fall under two types of architectures: the single instruction/multiple data (SIMD) stream architecture and the multiple instruction/multiple data (MIMD) stream architecture. A SIMD processor consists of many identical Arithmetic Units executing the same instruction, (but on different data), under the control of a single control unit. A MIMD processor is an asynchronous system where several processors, each executing a different instruction, independently process different data streams. Since the SIMD architecture does not replicate the control unit circuitry in each processor, it tends to be less complex than the MIMD architecture.
In a standard SIMD processor, a single Arithmetic Control Unit provides all the required control information in the form of global instructions to the Arithmetic Units (AU's). These Arithmetic Units, all which are identical, manipulate their own local data (the control and method of getting data to each AU may differ dependent upon the application), based upon the global instructions sent by the Arithmetic Control Unit. Since there is only one Arithmetic Control Unit for all of the Arithmetic Units, every Arithmetic Unit processes its data identically to all the other Arithmetic Units, although the results are different because the data in each AU are different. A standard SIMD processor cannot perform any data dependent algorithms. A data dpendent algorithm is a series of instructions whose instruction flow depends upon data values. This type of algorithm would be handled by using branch instructions in a von Neumann architecture, since there is no way to alter the instruction sequence from the Arithmetic Control Unit when all the possible data conditions in a data dependent algorithm may be present simultaneously in the Arithmetic Units.
FIG. 2 shows pictorially the structure of a data dependent algorithm. At step 2, a branch occurs, base upon the result of a previous instruction. Dependent upon that previously computed condition, either steps 3, 4, and 5 or steps 6 and 7 will be executed before step 8 is performed. Since the data in the memory of each AU can be any value, the standard SIMD processor is unable to perform a data dependent operation; some of the Arithmetic Units may need to traverse the left branch of an algorithm, while others need to traverse the right branch. Since there is only one instruction stream that controls the AU's, it is impossible for a standard SIMD processor to traverse both the left and right branches of an algorithm smmultaneously. The basic SIMD architecture, therefore, cannot perform this algorithm.
The initial conclusion is that SIMD processors are restricted to the class of non-data dependent algorithms, thereby relegating the data dependent algorithms to a processor more suited to performing them. Another option is to add additional functions to the basic SIMD architecture to allow a limited amount of data dependent operations to be performed. One method of adding this capability is by allowing the Arithmetic Control Unit to conditionally activate and deactivate each AU.
Conditional activate/deactivate circuitry in the Arithmetic Units allows them to activate or deactivate themselves based upon a data condition that exists within them. The instruction to conditionally activate or conditionally deactivate comes from the Arithmetic Control Unit, but only in the Arithmetic Units that the specified condition is true will the Arithmetic Unit become active or inactive, respectively. Only the Arithmetic Units that are active will interpret the instructions provided by the Arithmetic Control Unit and act upon them, whereas an inactive Arithmetic Unit will not act upon the instructions provided by the Arithmetic Control Unit (except, of course, it will act upon an instruction to activate itself). The conditional activate/deactivate function gives the capability of traversing, in turn, both branches of the algorithm structure of data dependent operations in a SIMD processor. This is done by serializing the algorithm flow (See FIG. 3) and deactivating the proper Arithmetic Units while traversing first the left side and then the right side of the algorithm structure. Although the conditional activate/deactivate function greatly increases the problem domain in which this modified SIMD processor is applicable, inefficiencies are introduced into the processing since all branch paths of the algorithm must be traversed, forcing Arithmetic Units to be inactive for some period of time, which decreases the overall processing speed of the computer.
In FIG. 3 an 8-step algorithm is illustrated where the activation or deactivation of the arithmetic units (AU) occurs at certain steps. As illustrated, the deactivation of all AU's that have a false condition for the illustrated algorithm will occur at step 2. At step 5 all AU's that had a Mue condition will be deactivated. Then at step 6 all AU's that had a false condition will be activated, and finally at step 7 all AU's will be activated.